// https://www.lintcode.com/problem/shortest-subarray-with-sum-at-least-k/description

// class Solution {
// public:
//     /**
//      * @param A: the array
//      * @param K: sum
//      * @return: the length
//      */
//     int shortestSubarray(vector<int> &A, int K) {
//         deque<int> tmp;
//         int sum = 0;
//         int cnt = 0;
//         int min_cnt = INT_MAX;
//         for (int i = 0; i < A.size(); ++i)
//         {
//             tmp.push_back(A[i]);
//             sum += A[i];
//             cnt++;
            
// // Input 可能有负数，不可以这样
// // Show Difference
// // [84,-37,32,40,95]
// // 167
// // Your stdout
// // 84
// // 47
// // 79
// // 119
// // 214
// // Output
// // 5
// // Expected
// // 3
//             while (!tmp.empty() && sum - tmp.front() > K)
//             {
//                 sum -= tmp.front();
//                 tmp.pop_front();
//                 cnt--;
//             }
//             cout << sum << endl;
//             if (sum >= K)
//             {
//                 min_cnt = min(min_cnt, cnt);
//             }
//         }
//         return min_cnt == INT_MAX ? -1: min_cnt;
//     }
// };

class Solution {
public:
    /**
     * @param A: the array
     * @param K: sum
     * @return: the length
     */
    // https://github.com/Shellbye/Shellbye.github.io/issues/41
     
    // 法一：dp
    int shortestSubarray(vector<int> &A, int K) {
        int n = A.size();
        int min_cnt = n + 1;
        vector<int> sum(n + 1, 0);
        for (int i = 0; i < n; i++) 
            sum[i + 1] = sum[i] + A[i];
        for (int i = 0; i < n; ++i)
        {
            for (int j = i + 1; j < n + 1; ++j)
            {
                if (sum[j] - sum[i] >= K)
                {
                    min_cnt = min(min_cnt, j - i);
                }
            }
        }
        return min_cnt == n + 1 ? -1: min_cnt;
    }
    
    // 前缀和数组正常用，deque记录的是可能的起始位置，而不是元素本身
    // int shortestSubarray(vector<int> &A, int K) {
    //     int n = A.size();
    //     int res = n + 1;
    //     vector<int> sum(n + 1, 0);
    //     for (int i = 0; i < n; i++) 
    //         sum[i + 1] = sum[i] + A[i];
    //     deque<int> d;
    //     for (int i = 0; i < n + 1; i++) {
    //         while (!d.empty() && sum[i] - sum[d.front()] >= K){
    //             res = min(res, i - d.front());
    //             d.pop_front();
    //         }
    //         // for (int i = 0; i < d.size(); ++i)
    //         // {
    //         //     cout << d[i] << endl;
    //         // }
    //         // cout << endl;
    //         while (!d.empty() && sum[i] <= sum[d.back()]) {
    //             d.pop_back();
    //         }
    //         d.push_back(i);
    //     }
    //     return res <= n ? res : -1;
    // }
};